package base.interesting;

import cn.hutool.core.util.NumberUtil;
import cn.hutool.core.util.ObjectUtil;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Stream;

/**
 * @program JavaBase
 * @description:
 * @author: zhanglu
 * @create: 2020-06-12 12:08:00
 */
public class Weidu60 {

    public static void test02(){
        Map<String, Double> mapper = new HashMap<>();
        List<Double> doubleList = new ArrayList<>();
        String str = "a0=18066650914796543948071  a1=4961777490995242981463  a2=31605894710659670798042  a3=19686130015871916084219  a4=18256239323596253089145  a5=17537800960575128076504  a6=18859418507418660312936  a7=19521586340613605744672  a8=26730286506050352820235  a9=8032588364104224461588  a10=1840922716355482931616  a11=6419609501035483180041  a12=3948072404005098735176  a13=1838790433991411941629  a14=4711355172321201666031  a15=37264884557667512875664  a16=6904712067937093179203  a17=7682194828047385922955  a18=7388233553702619882197  a19=25040824743906955624287  a20=27423370708457091582588  a21=17675564496306517442002  a22=8166693156373017495043  a23=17041706039422535601702  a24=9488530295635943421852  a25=20657408223760342396299  a26=32210688078864655919132  a27=18665103420448916974106  a28=5602106420273456829665  a29=32763161945048199529183  a30=24579593373533511023212  a31=1710066349530140264884  a32=29141054528624779377290  a33=13743893131855882059427  a34=20477633227602890278380  a35=3059396250506863050821  a36=27345810387400458342733  a37=28896952885900268580742  a38=13477378977933032248304  a39=10344684237990112205492  a40=17624458199694194392785  a41=32828480488681592364792  a42=23474826386291506828818  a43=8850468131553928519566  a44=22378644619164141533543  a45=5029089771033713500040  a46=8732360082744079013973  a47=17524256082007126150499  a48=15089924660009752103486  a49=1886578230024224850756  a50=31549726463695346873772  a51=1624490777692975580531  a52=37229670605205124877472  a53=17539434344401942893296  a54=5236004645028246582552  a55=2519243818222189488219  a56=658645589118087749659  a57=26508814276638093190214  a58=33787605402095509801095                         a59=32168716835058598606686";
        String[] s1 = str.split(" ");
        Stream.of(s1).forEach(s2 -> {
            String[] s3 = s2.split("=");
            String k = s3[0];
            String v = s3[1];
            Double dv = Double.valueOf(v);
            mapper.put(k, dv);
            doubleList.add(dv);
        });

        int n = 60;
        int k = 7;
        double s = 133588376232103627614352D;


        System.out.println(1);
    }

    public static int count = 0;

    public static void test03(int[] src, int currentSum, int index, int targetSum, int[] solution){
        count++;
        if(currentSum == targetSum){
            System.out.println("find");
            for (int i = 0; i < solution.length; i++) {
                if(solution[i] == 1){
                    System.out.print(src[i] + ",");
                }
            }
            System.out.println();
        }else if(index == src.length || currentSum > targetSum){
            return;
        }else {
            solution[index] = 1;
            currentSum += src[index];
            test03(src, currentSum, index + 1, targetSum, solution);
            currentSum -= src[index];
            solution[index] = 0;
            test03(src, currentSum, index + 1, targetSum, solution);
        }
    }

    public static void test04(double[] src, double currentSum, int index, double targetSum, int[] solution){
        count++;
        if(currentSum == targetSum){
            System.out.println("find");
            for (int i = 0; i < solution.length; i++) {
                if(solution[i] == 1){
                    System.out.print(src[i] + ",");
                }
            }
            System.out.println();
        }else if(index == src.length || currentSum > targetSum){
            return;
        }else {
            solution[index] = 1;
            currentSum += src[index];
            test04(src, currentSum, index + 1, targetSum, solution);
            currentSum -= src[index];
            solution[index] = 0;
            test04(src, currentSum, index + 1, targetSum, solution);
        }
    }

    public static boolean subSetDP(int[] A, int sum) {
        boolean[][] solution = new boolean[A.length + 1][sum + 1];
        // if sum is not zero and subset is 0, we can't make it
        for (int i = 1; i <= sum; i++) {
            solution[0][i] = false;
        }
        // if sum is 0 the we can make the empty subset to make sum 0
        for (int i = 0; i <= A.length; i++) {
            solution[i][0] = true;
        }

        //
        for (int i = 1; i <= A.length; i++) {
            for (int j = 1; j <= sum; j++) {
                // first copy the data from the top
                solution[i][j] = solution[i - 1][j];

                // If solution[i][j]==false check if can be made
                if (solution[i][j] == false && j >= A[i - 1])
                    solution[i][j] = solution[i][j] || solution[i - 1][j - A[i - 1]];
            }
        }

        for (int i = 0; i < A.length + 1; i++) {
            for (int j = 0; j < sum + 1; j++) {
                System.out.print(solution[i][j] + "\t");
            }
            System.out.println();
        }
        for (int i = 1; i < A.length + 1; i++) {
            for (int j = 1; j < sum + 1; j++) {
                if(solution[i][j] && !solution[i-1][j]){
                    System.out.print(A[i-1] + "\t");
                }
            }
        }

        return solution[A.length][sum];
    }

    public static void main(String[] args) {
        int[] a = {1,3,4,5};
        boolean b = subSetDP(a, 7);
        System.out.println("===");
        System.out.println(b);

        Map<String, Double> mapper = new HashMap<>();
        List<Double> doubleList = new ArrayList<>();
        String str = "a0=18066650914796543948071  a1=4961777490995242981463  a2=31605894710659670798042  a3=19686130015871916084219  a4=18256239323596253089145  a5=17537800960575128076504  a6=17537800960575128076504  a7=19521586340613605744672  a8=26730286506050352820235  a9=8032588364104224461588  a10=1840922716355482931616  a11=6419609501035483180041  a12=3948072404005098735176  a13=1838790433991411941629  a14=4711355172321201666031  a15=37264884557667512875664  a16=6904712067937093179203  a17=7682194828047385922955  a18=7388233553702619882197  a19=25040824743906955624287  a20=27423370708457091582588  a21=17675564496306517442002  a22=8166693156373017495043  a23=17041706039422535601702  a24=9488530295635943421852  a25=20657408223760342396299  a26=32210688078864655919132  a27=18665103420448916974106  a28=5602106420273456829665  a29=32763161945048199529183  a30=24579593373533511023212  a31=1710066349530140264884  a32=29141054528624779377290  a33=13743893131855882059427  a34=20477633227602890278380  a35=3059396250506863050821  a36=27345810387400458342733  a37=28896952885900268580742  a38=13477378977933032248304  a39=10344684237990112205492  a40=17624458199694194392785  a41=32828480488681592364792  a42=23474826386291506828818  a43=8850468131553928519566  a44=22378644619164141533543  a45=5029089771033713500040  a46=8732360082744079013973  a47=17524256082007126150499  a48=15089924660009752103486  a49=1886578230024224850756  a50=31549726463695346873772  a51=1624490777692975580531  a52=37229670605205124877472  a53=17539434344401942893296  a54=5236004645028246582552  a55=2519243818222189488219  a56=658645589118087749659  a57=26508814276638093190214  a58=33787605402095509801095                         a59=32168716835058598606686";
        String[] s1 = str.split(" ");
        Stream.of(s1).filter(o -> ObjectUtil.isNotEmpty(o)).forEach(s2 -> {
            String[] s3 = s2.split("=");
            try {
                String k = s3[0];
                String v = s3[1];
                Double dv = Double.valueOf(v);
                mapper.put(k, dv);
                doubleList.add(dv);
            } catch (Exception e) {
                e.printStackTrace();
            }
        });

        double[] src = new double[doubleList.size()];
        for (int i = 0; i < doubleList.size(); i++) {
            src[i] = doubleList.get(i);
        }
        int[] solution = new int[src.length];
        int n = 60;
        int k = 7;
        double s = 1.276522943770699E23;
        long start = System.currentTimeMillis();
        test04(src, 0, 0, s, solution);
        long end = System.currentTimeMillis();
        System.out.println("总计耗时：" + (end - start));
        System.out.println("遍历次数：" + count);

        double d1 = 18066650914796543948071D;
        double d2 = 4961777490995242981463D;
        double d3 = 31605894710659670798042D;
        double d4 = 19686130015871916084219D;
        double d5 = 18256239323596253089145D;
        double d6 = 17537800960575128076504D;
        double d7 = 17537800960575128076504D;
        System.out.println(Double.valueOf((d1 + d2 + d3 + d4 + d5 + d6 + d7)).toString());
    }

}
